编译原理(龙书)读书笔记

2023-08-01 01:17| 来源: 网络整理| 查看: 265

编译原理(龙书)读书笔记一、总结

编译原理主要讲述高级语言怎样通过一系列的转换和优化后生成机器语言的一门课程，学习编译原理后将会对整个编译流程和代码处理细节有更近一步的理解，后续如果需要更加一步的了解编译器工作的流程，建议配合链接器的相关资料进行阅读,市面上主推的有两本书《link and loader》和《程序员的自我修养》。

二、详细内容

编译器主要四个个步骤分别是:

词法分析；语法分析(中间代码生成)；中间代码优化；汇编；

下面将按照这四个步骤分别进行阐述:

2.1 词法分析

词法分析主要是为了识别高级语言中的关键字，常量，变量名，并将其信息保存在一个词法分析字典中再用一个词法单元对其进行索引，主要的识别算法就是NFA 和 DFA 两种实现方式，其中DFA是用来逻辑表示字符匹配的方法，最终代码实现是会将NFA 转为DFA 进行实现的，下面将列出几种和NFA和DFA之间的算法:

算法名描述子集法将NFA转换为DFADFA最小化将DFA化简为中间状态最少的DFA 2.2 语法分析

语法分析就是将词法分析后产生的词法单元，按照产生式的格式进行匹配并在匹配的过程中生成中间代码(一般生成的中间代码都不是汇编代码，通常都是四元式)·，语法分析主要实现算法和描述如下:

算法描述问题LL(0)最左推导(最右规约)算法，不会看当前产生式的FIRST集会存在无效递归和回退的尝试LL(1)最左推导(最右规约)算法，会查看当前产生式的FIRST集进行选择推导有些产生式会存在移入规约冲突LR(0)最左规约(最右推导)算法，不会查看当前产生式的FOLLOW集有些产生式会存在移入规约冲突SLR简单最左规约(最右推导)算法，会查看当前产生式的FOLLOW集有些产生式会存在移入规约冲突LALR向前看最左规约(最右推导)算法，根据LR(1)产生式合并同核心状态后的结果有些产生式会存在移入规约冲突LR(1)最左规约(最右推导)算法, 会查看当前产生式的FOLLOW集以及当前推到历史完整产生式的FOLLOW集产生的状态转换表一般较大，内存使用较多一般都未使用该种方式

在产生式进行规约的过程中，通过SDT方式进行翻译成四元式；

2.3 中间代码优化

通过语法分析后生成的四元式代码序列会被不同的Block 和 Region, 其中block中的代码执行序列是顺序执行不存在乱序和条件跳转的情况，Region则是包含很多个Block的执行块同时也是变量生存周期一个区间，下面将分别列出针对Block和Region 对象的优化算法:

Block 块中代码优化原则主要有如下几条:

删除公共子表达式;删除无用代码;常量合并;强度削弱；

主要实现方式是通过在Block中构建AST 树，然后通过AST树再反向映射会Block块;

Region 对象的优化算法:

代码移动;循环体展开；循环体合并；强度削弱(循环变量的仿射变换)；

Region 对象的优化算法有数据流图分析(每一个节点都是一个Block)和支配树(主要找出循环块)的寻找优化；

2.4 汇编

通过代码优化后的四元式可以直接进行直译方式转换为汇编代码，汇编代码在经过寄存器分配或者汇编指令优化后，通过汇编器转换为目标机器的代码，如果需要执行改代码还需要进过链接器的链接后才能生成操作系统可执行的代码；

【本文地址】

编译原理(龙书)读书笔记

编译原理(龙书)读书笔记

今日新闻

推荐新闻